package slidingwindow

import (
	"container/heap"
	"sort"
)

var a []int

type hp struct {
	sort.IntSlice   // 其实就是一个int[]，由于sort.IntSlice已经实现了Len，Swap，所以不需要实现了
}

func (h hp) Less(i, j int) bool { return a[h.IntSlice[i]] > a[h.IntSlice[j]] }  // 比较堆中两个元素的大小

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int))}

func (h *hp) Pop() any { a := h.IntSlice; v := a[len(a) - 1]; h.IntSlice = a[:len(a) - 1]; return v}

func maxSlidingWindow(nums []int, k int) []int {
	a = nums
	q := &hp{make([]int, k)}
	for i := 0; i < k; i++ {
		q.IntSlice[i] = i
	}
	heap.Init(q)  // heap.Init()接收一个实现了堆接口的结构体指针作为参数，堆这个结构体所代表的数据进行初始化，使其满足堆的特征
	n := len(nums)
	ans := make([]int, 1, n - k + 1)
	ans[0] = nums[q.IntSlice[0]]
	for i := k; i < n; i++ {
		heap.Push(q, i)
		for q.IntSlice[0] <= i - k {
			heap.Pop(q)
		}
		ans = append(ans, nums[q.IntSlice[0]])
	}
	return ans
}
